﻿// 走廊泼水节.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
* https://www.acwing.com/problem/content/348/
* 给定一棵 N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

输入格式
第一行包含整数 t，表示共有 t组测试数据。对于每组测试数据，第一行包含整数 N。

接下来 N−1 行，每行三个整数 X,Y,Z，表示 X 节点与 Y 节点之间存在一条边，长度为 Z。

输出格式
每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

数据范围
1≤N≤6000
1≤Z≤100

输入样例：
2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5 
输出样例：
4
17 


题意简述：
给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。所有边权均为整数。

解题思路：
- 题目要求加边后，原树仍然是唯一的最小生成树（MST）。
- 这意味着新加的每条边的权值必须大于等于树上两点间的最大边权，否则会破坏唯一性。
- 由于原图是一棵树，任意两点之间只有唯一一条路径，且路径上的最大边权就是它们间的瓶颈。
- 只需统计每对不连通分量之间的最小可加边权，累加即可。

本题不需要LCA（最近公共祖先）算法的原因：
- LCA常用于查询树上两点间的路径信息（如路径和、最大/最小值等）。
- 但本题采用Kruskal思想，按边权从小到大合并连通分量，每次合并时，分量内的所有点对之间的最大边权已知（即当前合并的边权）。
- 由于每次合并的分量是连通块，且合并顺序保证了边权递增，分量内的点对最大边权就是合并时的边权。
- 因此，不需要树上路径查询，也就不需要LCA，直接用并查集维护分量和大小即可。

*/

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_NODES = 6010;

// 边的结构体
struct Edge {
    int from, to, weight;
    const bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
} edges[MAX_NODES];

// 全局变量
int numNodes; // 节点数
int parent[MAX_NODES]; // 并查集父节点
int componentSize[MAX_NODES]; // 每个连通分量的大小

// 并查集查找
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

int main() {
    int testCases;
    cin >> testCases;

    while (testCases--) {
        // 输入节点数
        cin >> numNodes;

        // 初始化并查集
        for (int i = 1; i <= numNodes; i++) {
            parent[i] = i;
            componentSize[i] = 1;
        }

        // 输入边
        int edgeCount = numNodes - 1;
        for (int i = 0; i < edgeCount; i++) {
            int from, to, weight;
            cin >> from >> to >> weight;
            edges[i] = { from, to, weight };
        }

        // 按边权排序
        sort(edges, edges + edgeCount);

        // 计算结果
        int result = 0;
        for (int i = 0; i < edgeCount; i++) {
            int rootA = find(edges[i].from);
            int rootB = find(edges[i].to);
            int weight = edges[i].weight;

            if (rootA != rootB) {
                // 这里合并两个连通分量
                // 新加的边必须大于树上任意两点间的最大边权
                // 当前分量内任意点对的最大边权就是当前合并的边权
                // 所以新加的边权下界为 weight+1
                // 两分量间有 sizeA * sizeB 对点，每对只需加一条边（完全图），但树已连一条，剩下的就是 (sizeA * sizeB - 1)
                result += (componentSize[rootA] * componentSize[rootB] - 1) * (weight + 1);

                // 合并两个连通分量
                parent[rootA] = rootB;
                componentSize[rootB] += componentSize[rootA];
            }
        }

        // 输出结果
        cout << result << endl;
    }

    return 0;
}